package 剑指offer;

import java.util.Arrays;

public class p7重建二叉树 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder==null || preorder.length==0) {
            //边界条件 和 递归出口
            return null;
        }

        //创建根节点 并且 在inorder中找到根节点的下标index
        TreeNode root=new TreeNode(preorder[0]);
        int index=findIndex(preorder,inorder);

        //root.left=buildTree(左子树的前序数组，左子树的中序数组)
        root.left=buildTree(Arrays.copyOfRange(preorder,1,index+1),
                            Arrays.copyOfRange(inorder,0,index));
            //copyOfRange(int[] original, int from, int to)中 当from=to时，返回长度为0的数组,就会进入递归出口
        //root.right=buildTree(右子树的前序数组，右子树的中序数组)
        root.right=buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),
                             Arrays.copyOfRange(inorder,index+1,inorder.length));

        return root;
    }

    public static int findIndex(int[] preorder,int[] inorder) {
        for (int i = 0; i <preorder.length ; i++) {
            if (preorder[0]==inorder[i]) {
                return i;
            }
        }
        return -1;
    }
}
